package com.kenliang.algorithm.sort;

/**
 * @author KenLiang
 * @description:选择排序,时间复杂度O(N**2),空间复杂度O(1)，交换的数字可能破坏原来相等数字的顺序
 * @date Created in 14:52 2021/1/2.
 */
public class SelectSort implements ISort {


    @Override
    public int[] sort(int[] in) {
        //循环一次选出一个最大只放到最后,0～i-1位置的数字未排序
        for (int i = in.length; i > 0; i--) {
            int maxNumIndex = 0;
            //循环一次当前位置和最小值比较，记录最小值索引
            for (int j = 0; j < i ; j++) {
                if (in[maxNumIndex] < in[j]) {
                    maxNumIndex=j;
                }
            }
            this.swap(in,maxNumIndex,i-1);
        }
        return in;
    }

    public static void main(String[] args) {
        SelectSort selectSort = new SelectSort();
        int[] out = selectSort.sort(new int[]{3,6,455,3,2,1,5,634});
        for(int i:out){
            System.out.println(i);
        }
    }
}
